\documentclass{article}


\title{\textbf{Bachelor's thesis}\\Project proposal}
\author{Hylke Buisman\\ hbuisman@science.uva.nl}

\begin{document}
\maketitle

\setlength{\parindent}{0pt}
\setlength{\parskip}{0.3em}

\section{Introduction}
This document proposes the project which I, Hylke Buisman,
wish to complete in fulfillment of my Bachelor's thesis.

The main goal of this project is to propose an algorithm
for Qualitative System Identification. In other words,
this project will make a step toward solving the question:
How can a system's structure be determined given a set of behaviours?

\section{Problem statement}

In this section the motivation for this project will be explained. 
In addition it will be made clear why an algorithm that solves this question
will indeed be a novel constribution to the current approaches for system identification.

\subsection{Motivation}
As humans we have always been observing the objects and processes
around us, and how they interact in a meaningful way. From these
observations we create notion of which objects and processes `belong together'.
That is, we cluster the behaviour of the world around us in systems.
After observing a kettle on a stove, we conceptually form a model 
of the structure that underlies this behaviour. With these models we can
reason about causes and effects related to this behaviour. It can be argued
that this skill is a major part of human understanding, and at least plays
an important role in how we can interact with our environment by being able to predict what will
happen.

Similarly, in order for artificial agents, such as robots, to be able to survive in an unknown environment
or to handle unknown processes, building an understanding of observed behaviour is crucial. 
For example, a robot that is dropped on an unknown planet should be able to learn how
its new environment behaves by determining how the planet's physical laws guide behaviour.
In such a situation the only input that can aid the agent is an observation of the behaviour.

In addition another important motivation can be identified. Prior research (e.g. \cite{bredeweg2004qme}) indicates
that qualitative models can facilitate knowledge transfer and acquisition. In such a setting a domain expert
would typically build a QR model, which is than studied or used for simulation. 
However, these domain experts are seldom experienced in QR modeling and the modelling
process is often experienced as difficult. Thus, an algorithm that can build such a model given a 
(detailed) behaviour description would greatly relieve the strain placed on these experts and speed up the modeling process.


\subsection{Problem}
Given this setting, the problem becomes apparent: how can we derive the structure that underlies
an observed behaviour? The problem of deriving structure from behaviour is not entirely new.
The field of System Identification \cite{LjungSID} aims to build dynamical models from measured data.
However, this approach is mainly mathematical, producing ordinary differential equations (ODEs) that underly
the measured data. Although these ODEs in some sense explain the data, they do not give any insight
in the causalities in the system. In addition these methods don't easily handle incomplete
or noisy data. Already one step closer to solving the problem is the 
field of Qualtitative System Identification. By abstracting from quantitative data to qualitative data,
an intuitive intrepretation of the data can be made. These models use Qualitative Reasoning (QR)
to find Qualitative Differential Equations (QDEs) to describe the underlying structure.
However, these models are generally based on Kuipers' constraint based approach to QR, which is still
rather mathematically inclined and does not allow for an intuitive representation of causality.

Thus, it is clear that a novel approach is desired that can derive a system's structure 
while also making explicit the system's causal relations. 

\section{Goals}
The best available formalism for tackling this problem is Forbus' process based approach to QR.
Since no System Identification methods are available for Forbus' approach, this project
will have as goal to construct such an algorithm.

To make the problem more tractable the method will have to make
several assumptions regarding the input. An example is that there should be no noise
in the data, and a representation of all possible behaviours (full envisionment) is given as input. 
Future work may loosen these assumptions to generate a more robust algorithm.

The goals is not to develop a fully fledged, robust algorithm, since that is to much
for the time available for this project.

\section{Method}

The preliminary ideas regarding the method approach the problem by searching through the space of possible models.
This search is guided by using inference knowledge of the GARP3 \cite{bredeweg2006gnw} QR engine.
Using each state's quantity values, derivative values, (in)equalities and the inference knowledge, dependencies
can be added to a model. By building models in this way, a large set of models is the result.
To ensure that it stays computationally tractable, the search tree should be pruned early on in
the search. A heuristic will additionaly be necessary to guide the search. The focus will
most definitely lie on finding good heuristics for guiding the search.

Depending on the type of search algorithm a set of models is returned that most likely 
reflect the structure of the system underlying the input data. Using a ranking function
and possibly by comparing the models output behaviour with the input behaviour, the best
model can be selected.

The final evaluation of the algorithm will be based by testing it on a set of models
that is made available on the GARP3 Qualitative Reasoning and Modelling (QRM) portal \cite{garp3website}.


\section{Resources}
A total of eight weeks of full-time work by one person is available to achieve the project's goals. 
Of these eight weeks, two have already been used for exploration of the domain. The remaining six
weeks will be used for the creation of the algorithm.


\bibliographystyle{plain}
\bibliography{ref}

\end{document}